package offer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author Elephas
 * @Date 2022/2/6
 **/
@FunctionalInterface
public interface SumOfUnique {
    /**
     * You are given an integer array nums.
     * The unique elements of an array are the elements that appear exactly once in the array.
     *
     * Return the sum of all the unique elements of nums.
     *
     * @param nums
     * @return
     */
    int sumOfUnique(int[] nums);
}
class SumOfUniqueImpl1 implements SumOfUnique{
    static final int[] TEST_01 = new int[]{1,2,3,2};
    static final int[] TEST_02 = new int[]{1,1};
    static final int[] TEST_03 = new int[]{1,2};
    static final int[] TEST_04 = new int[]{1,1,1};
    static final int[] TEST_05 = new int[]{1,2,2};
    static final int[] TEST_06 = new int[]{1,2,3};
    static final int[][] TESTS = new int[][]{TEST_01,TEST_02,TEST_03,TEST_04,TEST_05,TEST_06};
    static final int[] ANSWERS = new int[]{4,0,3,0,1,6};
    public static void main(String[] args) {
        for (int i = 0; i < TESTS.length; i++) {
            int curAns = new SumOfUniqueImpl1().sumOfUnique(TESTS[i]);
            int curTest = ANSWERS[i];
            System.out.println(curAns == curTest);
        }
    }

    /**
     * o(nlogn),o(1)
     * Sort the array, then sum the unique elements.
     * @param nums
     * @return
     */
    public int sumOfUnique(int[] nums){
        if(nums.length == 0){
            return 0;
        }else if(nums.length == 1){
            return nums[0];
        }else{
            Arrays.sort(nums);
            int curSum = 0;
            int firstElement = nums[0];
            int secondElement = nums[1];
            if(firstElement != secondElement){
                curSum += firstElement;
            }
            for (int i = 1; i < nums.length - 1; i++) {
                int preElement = nums[i - 1];
                int curElement = nums[i];
                int nextElement = nums[i + 1];
                if(curElement != nextElement && curElement != preElement){
                    curSum += curElement;
                }
            }
            int lastElement = nums[nums.length - 1];
            int secondLastElement = nums[nums.length - 2];
            if(lastElement != secondLastElement){
                curSum += lastElement;
            }
            return curSum;
        }
    }
}

class SumOfUniqueImpl2 implements SumOfUnique{
    /**
     * o(n), o(n)
     * use a map to get the appear frequencies of each element, then sum the unique element.
     * @param nums
     * @return
     */
    @Override
    public int sumOfUnique(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int curElement = nums[i];
            int freq = map.getOrDefault(curElement,0);
            map.put(curElement, freq + 1);
        }
        int sum = 0;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            int curElement = entry.getKey();
            int frequency = entry.getValue();
            if(frequency == 1){
                sum += curElement;
            }
        }
        return sum;
    }
}

class SumOfUniqueImpl3 implements SumOfUnique{

    /**
     * 官方题解，一次遍历
     * @param nums
     * @return
     */
    @Override
    public int sumOfUnique(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        int sum = 0;
        for(int num : nums){
            int freq = map.getOrDefault(num,0);
            if(freq == 0){
                sum += num;
            }else if(freq == 1){
                sum -= num;
            }
            map.put(num,freq + 1);
        }
        return sum;
    }
}